﻿////// --------------------------------------------------------------------------------------------------------------------
////// <copyright file="LeftLeaningTreeBase.cs" company="Team Awesome">
//////   Awesome
////// </copyright>
////// <summary>
//////   Defines the LeftLeaningTreeBase type.
//////
//////	 Commented out until work is resumed to avoid an overflow of warnings.
////// </summary>
////// --------------------------------------------------------------------------------------------------------------------

////namespace System.Collections
////{
////    using Diagnostics.Contracts;

////    /// <summary>
////    /// Base class for left leaning trees
////    /// </summary>
////    internal abstract class LeftLeaningTreeBase : TreeBase
////    {
////        /// <summary>
////        /// Gets or sets Root.
////        /// </summary>
////        protected abstract RedBlackTreeNode Root { get; set; }

////        #region ContractInvariantMethod

////        // ReSharper disable UnusedMember.Local

////        /// <summary>
////        /// This method is used by code contracts to set all the invariants for the class.
////        /// </summary>
////        [ContractInvariantMethod]
////        private void ObjectInvariant()
////        {
////            //// 1. A node is either red or black. - Is true because color is represented as a boolean.
////            //// 2. The root is black. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
////            Contract.Invariant(Root == null || !Root.IsRed);
////            //// 3. All leaves are black. - In our implementation every leaf is the value null and represents the black nil.
////            //// 4. No path from the root to the bottom contains two consecutive red links.
////            //// &  There can't be any right leaning 3 nodes or 4 nodes in a 2-3 LLRB tree.
////            string failureCondition;
////            Contract.Invariant(CheckTreeColourStructure(out failureCondition), failureCondition);
////            //// 5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
////            Contract.Invariant(EqualAmountOfBlackNodes());
////        }

////        /// <summary>
////        /// Gets the number of black children or returns -1 if they haven't been equal from bottom up.
////        /// </summary>
////        /// <param name="node">
////        /// The node.
////        /// </param>
////        /// <returns>
////        /// Number of black children and -1 if they havent been equal from bottom up.
////        /// </returns>
////        [Pure]
////        [ContractRuntimeIgnored]
////        private static int AmountOfBlackChildren(RedBlackTreeNode node)
////        {
////            if (node == null)
////                return 0;

////            var leftBlackChildren = AmountOfBlackChildren(node.Left);
////            var rightBlackChildren = AmountOfBlackChildren(node.Right);

////            if (leftBlackChildren == -1 || rightBlackChildren == -1 || leftBlackChildren != rightBlackChildren)
////                return -1;

////            var blackChildren = leftBlackChildren + rightBlackChildren;

////            return blackChildren + (!node.IsRed ? 1 : 0);
////        }

////        /// <summary>
////        /// Checks if there is the same amount of black notes in the left and right subtree from every subtree in the tree.
////        /// </summary>
////        /// <returns>
////        /// A boolean stating if there is the same amount of black notes in the left and right subtree from every subtree in the tree.
////        /// </returns>
////        [Pure]
////        [ContractRuntimeIgnored]
////        private bool EqualAmountOfBlackNodes()
////        {
////            return -1 != AmountOfBlackChildren(Root);
////        }

////        /// <summary>
////        /// Checks if the tree is without 4 nodes or right leaning 3 nodes. That is, if any node has a red child to the right.
////        /// </summary>
////        /// <param name="failureCondition">
////        /// The failure Condition to be posted if the method return false.
////        /// </param>
////        /// <returns>
////        /// Returns false if a 4 node or right leaning 3 node is found. Else true.
////        /// </returns>
////        [Pure]
////        [ContractRuntimeIgnored]
////        private bool CheckTreeColourStructure(out string failureCondition)
////        {
////            return CheckTreeColourStructure(Root, out failureCondition);
////        }

////        /// <summary>
////        /// Makes sure the tree does not contain any right leaning 3 nodes. That is, if any node has a red child to the right.
////        /// or
////        /// Makes sure the tree does not contain any 4 nodes. That is, if a node has 2 red children.
////        /// and
////        /// Makes sure the tree does not contain two concussive red nodes. A red node must not have a red child.
////        /// </summary>
////        /// <param name="h">
////        /// The node which to check if its subtrees contains 4 nodes or right leaning 3 nodes.
////        /// </param>
////        /// <param name="failureCondition">
////        /// The failure Condition.
////        /// </param>
////        /// <returns>
////        /// Returns false if a 4 node or right leaning 3 node is found. Else true.
////        /// </returns>
////        [Pure]
////        [ContractRuntimeIgnored]
////        private static bool CheckTreeColourStructure(RedBlackTreeNode h, out string failureCondition)
////        {
////            if (h == null)
////            {
////                failureCondition = TreeColourStructureCondition.NoFailure;
////                return true;
////            }

////            // Is right leaning 3 node or 4 node
////            if (h.Right != null && h.Right.IsRed)
////            {
////                failureCondition = TreeColourStructureCondition.RightLeaningOrFourNode;
////                return false;
////            }

////            // There are two red nodes in a row
////            if (h.IsRed && h.Left != null && h.Left.IsRed)
////            {
////                failureCondition = TreeColourStructureCondition.TwoRedNodesInARow;
////                return false;
////            }

////            return CheckTreeColourStructure(h.Left, out failureCondition) && CheckTreeColourStructure(h.Right, out failureCondition);
////        }

////        /// <summary>
////        /// Failure condition for invariance check methods.
////        /// </summary>
////        private static class TreeColourStructureCondition
////        {
////            /// <summary>
////            /// Succeeded state.
////            /// </summary>
////            public const string NoFailure = "Succeeded.";

////            /// <summary>
////            /// A node had a right red child.
////            /// </summary>
////            public const string RightLeaningOrFourNode = "A node had a right red child";

////            /// <summary>
////            /// A node and its child are both red.
////            /// </summary>
////            public const string TwoRedNodesInARow = "A node and its child are both red.";
////        }

////        // ReSharper restore UnusedMember.Local
////        #endregion

////        #region Node

////        /// <summary>
////        /// Validates the node and return true if it is red.
////        /// </summary>
////        /// <param name="node">
////        /// The node.
////        /// </param>
////        /// <returns>
////        /// True if node.IsRed is true.
////        /// </returns>
////        [Pure]
////        protected static bool IsColourRed(RedBlackTreeNode node)
////        {
////            #region Code Contracs: Pre - and Post conditions

////            Contract.Ensures(Contract.Result<bool>() == (Contract.OldValue(node) != null && Contract.OldValue(node).IsRed));

////            #endregion

////            return node != null && node.IsRed;
////        }

////        /// <summary>
////        /// A red black tree node.
////        /// </summary>
////        protected class RedBlackTreeNode : BinaryTreeNode
////        {
////            /// <summary>
////            /// Initializes a new instance of the <see cref="RedBlackTreeNode"/> class.
////            /// </summary>
////            /// <param name="item">
////            /// The data item.
////            /// </param>
////            protected RedBlackTreeNode(int item)
////                : base(item)
////            {
////            }

////            /// <summary>
////            /// Gets or sets left node.
////            /// </summary>
////            public new RedBlackTreeNode Left { get; set; }

////            /// <summary>
////            /// Gets or sets right node.
////            /// </summary>
////            public new RedBlackTreeNode Right { get; set; }

////            /// <summary>
////            /// Gets or sets a value indicating whether this node is black (or red).
////            /// </summary>
////            public bool IsRed { get; set; }
////        }

////        #endregion
////    }
////}